CONTINUACIONES (CONTINUATION- PASSING STYLE, CPS)

Parametrización funcional de funciones
“Continuation-passing style es una notación de programa que hace explícito cada aspecto del flujo de control y de datos” (Andrew W. Appel)

---

La Técnica CPS
Definición

CPS es una técnica de programación funcional que consiste en lo siguiente:

• En una función f(x), de parámetro(s) x, se incluye un parámetro extra c, que representa una función más general, es decir, f(x, c).
  
  
• La nueva función, con argumentos a y c, no devuelve el resultado r = f(a), sino el resultado de aplicar la función c a r, es decir, c(r) = c(f(a)). En general, f(x, c) = c(f(x)).

La función c con argumento r representa lo que “falta por hacer” (tras la obtención del primer resultado r) para completar el resultado final de la función f. Es por ello que a c se le denomina “función continuación” o, simplemente, “continuación”. Y a la función que incluye como parámetro una función continuación se le denomina “función con continuación” o “función CPS”.


Diferencia entre las funciones f(a, c) y c(f(a))

En ambos casos el resultado es el mismo, pero hay importantes diferencias:

1. En la primera función, c es un parámetro y en la segunda no.
   
   
2. En la primera función, tras la ejecución y obtención del resultado r, se invoca a c (con argumento r). Posteriormente se devuelve el control. En la segunda función, tras la obtención de r, hay retorno (del resultado y del control) a la función c.
   
   
3. En el primer caso, puede haber continuaciones de orden superior, es decir, la continuación podría invocar a su vez a otra función con continuación, que a su vez podría llamar a otra función con continuación, etc., por lo que la función está funcionalmente abierta. En el segundo caso, la función está funcionalmente cerrada.

Implementación en MENTAL
Especificación

La función CPS en MENTAL se puede representar de la forma clásica (con los parámetros entre paréntesis) f(x c) siendo:

x: parámetro(s) de la función f.
c: función continuación.

Definición:

⟨( f(x c) = c(f(x)) )⟩

Ejemplo

1. Estilo normal.
   
   Definición de función:
   ⟨( cuadrado(x) = x*x )⟩
   
   Uso de la función:
   cuadrado(4) // ev. 4*4 ev. 16
   
   
2. CPS.
   
   Definición de función (se añade un parámetro adicional):
   ⟨( cuadrado(x c) = c(x*x) )⟩
   
   Definición de una función continuación:
   ⟨( sumar5(x) = x+5 )⟩
   
   Uso de la función:
   cuadrado(4 sumar5) // ev. sumar5(4*4) ev. sumar5(16) ev. 16+5 ev. 21
   
   Definición de otra función continuación:
   ⟨( prod5(x) = 5*x )⟩
   
   Uso de la función con la nueva función continuación:
   cuadrado(4 prod5) // ev. prod5(4*4) ev. prod5(16) ev. 5*16 ev. 80

Función continuación con parámetros

La función c representa a una función de cualquier número de parámetros. Por ejemplo, generalizando el ejemplo anterior mediante un parámetro,

⟨( sumar(n)(x) = x+n )⟩

cuadrado(4 sumar(23)) // ev. sumar(23)(4*4) ev. 16+23 ev. 39

Un ejemplo de función continuación con dos parámetros es el siguiente:

⟨( lineal(a b)(x) = (a*x + b) )⟩

cuadrado(4 lineal(2 5)) // ev. lineal(2 5)(4*4) ev. 2*16 + 5 ev. 37

Obsérvese que es necesario separar los parámetros propios de la función continuación del parámetro correspondiente al resultado de la función CPS.


Continuación nula

En la función CPS

⟨( cuadrado(x c) = c(x*x) )⟩

si utilizamos como continuación la expresión nula (θ), tenemos, por ejemplo:

cuadrado(4 θ) // ev. cuadrado(4)

Por lo tanto, cuando la continuación es nula, estamos en el estilo normal.


Variables ligadas y libres en CPS

Una función CPS −como toda expresión genérica parametrizada− tiene variables de dos tipos:

• Ligadas. Son los parámetros utilizados por las funciones CPS y por las continuaciones.
• Libres. Son las variables del espacio abstracto.

Ejemplo:

(u=7 v=2 w=5)
⟨( fun(x c) = c(x + w) )⟩ // ligadas: x, c libres: w
⟨( cont(x) = (u*x + v) )⟩ // ligadas: x libres: u, v

fun(4 cont) // ev. cont(4+5) ev. cont(9) ev. (7*9 + 2) ev. 65

Continuación en funciones recursivas

La aplicación de una continuación a una función recursiva produce una nueva función (extendida) que se aplica a la función recursiva original.

Ejemplo con factorial:

1. Estilo normal:
   
   ⟨( fac(n) = (1 ← n=1 →' n*fac(n−1)) )⟩

fac(4) // ev. 4*3*2*1 ev. 24
   
   
2. CPS:
   
   ⟨( facx(n c) = (c(fac(n)) )⟩
   
   Si utilizamos la función continuación
   
   ⟨( lineal(a b)(x) = (a*x + b) )⟩
   
   tenemos:
   
   facx(4 lineal(2 5)) // ev. lineal(2 5)(24) ev. 224+5 ev. 53

Ejemplo con la secuencia de Fibonacci: 1, 1, 2, 3, 5, 8, 13, …

1. Estilo normal:
   
   ⟨( fibo(n) = (1 ← n>2 →' (fibo(n−1) + fibo(n−2))) )⟩

fibo(1) // ev. 1
fibo(2) // ev. 1
fibo(3) // ev. 2
fibo(4) // ev. 3
fibo(5) // ev. 5
...
   
   
2. CPS:
   
   ⟨( fibox(n c) = c(fibo(n)) )⟩
   
   Si utilizamos la función continuación
   
   ⟨( doble(x) = 2*x )⟩
   
   tenemos:
   
   fibox(1 doble) // ev. doble(1) ev. 2
fibox(2 doble) // ev. doble(1) ev. 2
fibox(3 doble) // ev. doble(2) ev. 4
fibox(4 doble) // ev. doble(3) ev. 6
fibox(5 doble) // ev. doble(5) ev. 10
...
   
   Lo que se obtiene son los valores dobles de la secuencia de Fibonacci.

Continuaciones de orden superior

Una función continuación puede, a su vez, tener otra función continuación. La forma general para dos funciones continuación es

⟨( f(x c1 c2) = c2(c1(f(x))) )⟩

Por ejemplo:

⟨( cuadrado(x c1 c2) = c1(x*x c2)) )⟩ // eq.
⟨( cuadrado(x c1 c2) = c2(c1(x*x)) )⟩

Definición de una función continuación c1:

⟨( sumar5(x) = x+5 )⟩

Definición de una función continuación c2:

⟨( prod3(x) = 3*x) )⟩

Uso de la función:

cuadrado(4 sumar5 prod3)) // ev. prod3(sumar5(4*4)) // ev. prod3(16+5) ev. prod3(21) ev. 63

Las funciones continuación de orden superior podrían tener, a su vez, parámetros.


Más allá de CPS. La parametrización de expresiones

La técnica CPS es la parametrización funcional de funciones, pero es un caso particular del caso general de adición de parámetros a expresiones, que puede hacerse en MENTAL.

• Se pueden parametrizar todo tipo de expresiones (funciones, reglas, objetos, datos, etc.).
  
  
• Los parámetros se pueden insertar en puntos estratégicos que faciliten su utilización posterior de una manera más genérica.
  
  
• Un mismo parámetro se puede instanciar como función o como dato.
  
  
• Pueden añadirse todos los parámetros que se deseen a las expresiones.

Ejemplos de función sobre resultados intermedios (no sobre el resultado final):

1. Factorial:
   
   ⟨( fac(n c) = (c(1) ← n=1 →' c(n)*fac(n−1 c))) )⟩
   
   
   fac(1 c) // ev. c(1)
fac(2 c) // ev. c(2)*c(1)
fac(3 c) // ev. c(3)*c(2)*c(1)
...
   
   Si c=θ, tenemos la función factorial normal.
   
   Si utilizamos la función ⟨( doble(x) = x*2 )⟩, tenemos:
   
   
   fac(1 doble) // ev. doble(1) ev. 2

fac(2 doble) // ev. doble(2)*doble(1) ev. 4*2 ev. 8

fac(3 doble) // ev. doble(3) * doble(2) * doble(1) ev. 6*4*2 ev. 48 ...
   
   
2. Secuencia de Fibonacci: 1, 1, 2, 3, 5, 8, 13, ...
   
   ⟨( fibo(n c) = (c(1) ← n>2 →' c(fibo(n−1 c) + fibo(n−2 c)))) )⟩
   
   
   fibo(1 c) // ev. c(1)
fibo(2 c) // ev. c(1)

fibo(3 c) // ev. c(fibo(2 c) + fibo(1 c)) ev. c(2*c(1))

fibo(4 c) // ev. c(fibo(3 c) + fibo(2 c)) ev. c(c(2*c(1)) + c(1))
...
   
   Si c=θ, tenemos la función de Fibonacci normal.
   
   Si utilizamos la misma función anterior (doble) como c, tenemos:
   
   
   fibo(1 doble) // ev. doble(1) ev. 2

fibo(2 doble) // ev. doble(1) ev. 2

fibo(3 doble) // ev. doble(2 + 2) ev. 8

fibo(4 doble) // ev. doble(2 + 8) ev. 20
...

Ejemplos de parametrización de datos:

1. ⟨(unodos(c) = c(12))⟩
   
   Parametrización mediante una función:
   
   
   ⟨(doble(x) = 2*x)⟩

unodos(doble) // ev. 2*12 ev. 24
   
   Parametrización mediante datos:
   
   
   unodos(123) // ev. 123(12)
   
   
2. ⟨( registro(c) = (c(6) c(12) c(9) c(17) c(8)) )⟩
   
   Parametrización mediante una función:
   
   
   ⟨( selec(n)(x) = (x<n → x) )⟩ // selecciona x si menor que n

registro(selec(10)) // ev. (6 9 8)
   
   Parametrización mediante datos:
   
   
   registro(abc)) // ev. (abc(6) abc(12) abc(9) abc(17) abc(8))
   
   
3. ⟨( registro(c) = (6 12 9 17 8)c )⟩
   
   Parametrización mediante una función:
   
   
   ⟨( selec(s)(x) = ( x⇓s ) )⟩ // s es el criterio de selección

registro(selec(>9)) // ev. (6 12 9 17 8)⇓(>9) ev. (12 17)
   
   Parametrización mediante datos:
   
   
   registro(u v w) // ev. (6 12 9 17 8)(u v w)

Conclusiones

En los lenguajes de programación tradicionales, f es fijo (no puede ser variable). En MENTAL, sí puede ser variable, por lo que el concepto de continuación es irrelevante, pues da lo mismo incluir la continuación como parámetro o como función. Por ejemplo,

⟨( cuadrado(x) = x*x )⟩
⟨( doble(x) = x*2 )⟩
⟨( f(x c) = c(f(x) )⟩

Nombre de la función variable:

(f = cuadrado)
f(5 c) // ev. cuadrado(5 c)) ev. c(cuadrado(5)) ev. c(25)

Nombre de la función continuación variable:

(c = cuadrado)
f(5 c) // ev. f(5 cuadrado) ev. cuadrado(f(5)) ev. f(5)*f(5)

Nombre de la función variable y nombre de la función continuación variable:

(f = cuadrado)
(c = doble)
f(5 c) // ev. cuadrado(5 doble) ev. doble(cuadrado(5)) ev. doble(25) ev. 50

---

Adenda
Características principales de la técnica CPS

• La técnica CPS se puede considerar como una bifurcación (goto) parametrizada de alto nivel, pues una llamada a una función de continuación es realmente un salto a otra parte del programa.
  
  
• Al introducir un parámetro adicional en la definición de funciones, éstas se generalizan. Otra forma de verlo es decir que el lenguaje original se extiende y se hace más flexible.
  
  Paradójicamente, al mismo tiempo, nos podemos encontrar con un entorno de menor nivel de abstracción, de mayor detalle, pues se hacen explícitas las secuencias de computación. Es por ello que esta técnica se utiliza internamente en compiladores e intérpretes de lenguajes de programación, especialmente funcionales, para aproximar sucesivamente un lenguaje de alto nivel a otro de bajo nivel (como es el código de máquina) mediante secuencias de expresiones.
  
  De hecho, se puede establecer una cierta analogía entre un programa realizado con continuaciones y una máquina tipo von Neumann, en donde las secuencias de ejecución CPS corresponderían a las instrucciones y las variables a los registros de la máquina.
  
  
• Si un programa se realiza totalmente con continuaciones, entonces se eliminan totalmente los retornos (de control y de valores). Por consiguiente, no hay necesidad de utilizar internamente una pila para el almacenamiento de estos valores, por lo que dicha implementación es más sencilla.
  
  La ejecución consistiría en una secuencia de la forma
  
  
  (f1(a1 c1) f2(a2 c2) f3(a3 c3) …)
  
  siendo:
  
  
  fi: función con continuación
  ai: argumento(s)
  ci: continuación
  
  El entorno se arrastra de un elemento al siguiente y las llamadas y los datos se hacen explícitos.
  
  CPS tiene el efecto de linealizar la ejecución de un programa, frente al sistema de programación clásico, que podemos calificar de “reactivo”, pues a cada llamada corresponde un retorno con una respuesta.
  
  Cualquier función tradicional se puede reescribir en CPS, por lo que es posible desechar la pila completamente y usar solo continuaciones.
  
  
• La técnica CPS tiene ventaja sobre las funciones normales cuando el resultado de la función implica una gran cantidad de datos, pues no hay necesidad de agruparlos para devolverlos como resultado ni hay necesidad de recogerlos en la función llamadora.
  
  
• Lo que se obtiene con la técnica CPS no es una función de orden superior (función de función), pues este concepto corresponde al de una función en la que los parámetros son funciones y el resultado es otra función.

Aplicaciones de la técnica CPS

La técnica CPS nació a finales de los años 1960s. Desde entonces, además de su aplicación mencionada en el desarrollo de compiladores e intérpretes, también se ha aplicado en diversidad de áreas:

• Transformación de programas.
• Generadores.
• Excepciones.
• Llamadas a procedimientos remotos.
• Computación persistente.
• Programación concurrente.
• Programación orientada a eventos.
• Etc.

Bibliografía

• Applel, Andrew W. Compiling with Continuations. Cambridge University Press, 1992.
  
  
• Friedman, D.P.; Wand, M.; Heynes, C.T. Essentials of Programming Languages. The MIT Press, 1992. [Cubre el tema CPS en profundidad con el lenguaje functional Scheme.]
  
  
• Jones, Neil. D.; Gomard, Carsten K.; Sestoff, Meter. Partial Evaluation and Automatic Program Generation. Prentice Hall International Series in Computer Science, 1993. [Se estudia CPS como técnica en la generación de programas.]
  
  
• Kalsey, Richard A. A correspondence between continuation passing style and static single assignement form. ACM SIGPLAN Notices, 30(3): 13-22, March 1995.
  
  
• Sabry, Amr; Felleisen, Mathias. Reasoning about programs in continuation-passing style. Lisp and Symbolic Computation, 6(3-4):289-360, 1993.
  
  
• Stansifer, Ryan. The Study of Programming Languages. Prentice-Hall, New Jersey, 1995. [Trata el tema CPS en el contexto del cálculo lambda.]